    #include "stdafx.h"   
    #include "置换算法.h"   
    #include "置换算法Dlg.h"   
      
    #ifdef _DEBUG   
    #define new DEBUG_NEW   
    #undef THIS_FILE   
    static char THIS_FILE[] = __FILE__;   
    #endif   
      
    /////////////////////////////////////////////////////////////////////////////   
    // CAboutDlg dialog used for App About   
      
         CRect rectSmall;  //收缩   
         CRect rectLarge;  //扩展   
         CRect rectrang_1;  //边缘           
        bool flag=true;   
        int i,j,k,m;   
            int visit[19];   //访问数组   
        int *count;  //停留标记   
        int *mem;  //内存分配页   
    int FIFO(int *count_0,int num);   
    int OPT(int *count_0,int i,int num,int *vis);   
    class CAboutDlg : public CDialog   
    {   
    public:   
        CAboutDlg();   
      
    // Dialog Data   
        //{{AFX_DATA(CAboutDlg)   
        enum { IDD = IDD_ABOUTBOX };   
        //}}AFX_DATA   
      
        // ClassWizard generated virtual function overrides   
        //{{AFX_VIRTUAL(CAboutDlg)   
        protected:   
        virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support   
        //}}AFX_VIRTUAL   
      
    // Implementation   
    protected:   
        //{{AFX_MSG(CAboutDlg)   
        //}}AFX_MSG   
        DECLARE_MESSAGE_MAP()   
    };   
      
    CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)   
    {   
        //{{AFX_DATA_INIT(CAboutDlg)   
        //}}AFX_DATA_INIT   
    }   
      
    void CAboutDlg::DoDataExchange(CDataExchange* pDX)   
    {   
        CDialog::DoDataExchange(pDX);   
        //{{AFX_DATA_MAP(CAboutDlg)   
        //}}AFX_DATA_MAP   
    }   
      
    BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)   
        //{{AFX_MSG_MAP(CAboutDlg)   
            // No message handlers   
        //}}AFX_MSG_MAP   
    END_MESSAGE_MAP()   
      
    /////////////////////////////////////////////////////////////////////////////   
    // CMyDlg dialog   
      
    CMyDlg::CMyDlg(CWnd* pParent /*=NULL*/)   
        : CDialog(CMyDlg::IDD, pParent)   
    {   
        //{{AFX_DATA_INIT(CMyDlg)   
        m_suanfa = -1;   
        //}}AFX_DATA_INIT   
        // Note that LoadIcon does not require a subsequent DestroyIcon in Win32   
        m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);   
    }   
      
    void CMyDlg::DoDataExchange(CDataExchange* pDX)   
    {   
        CDialog::DoDataExchange(pDX);   
        //{{AFX_DATA_MAP(CMyDlg)   
        DDX_Control(pDX, IDC_rang, m_rang);   
        DDX_Radio(pDX, IDC_RADIO1, m_suanfa);   
        //}}AFX_DATA_MAP   
    }   
      
    BEGIN_MESSAGE_MAP(CMyDlg, CDialog)   
        //{{AFX_MSG_MAP(CMyDlg)   
        ON_WM_SYSCOMMAND()   
        ON_WM_PAINT()   
        ON_WM_QUERYDRAGICON()   
        ON_WM_MOUSEMOVE()   
        ON_BN_CLICKED(IDC_queding, Onqueding)   
        //}}AFX_MSG_MAP   
    END_MESSAGE_MAP()   
      
    /////////////////////////////////////////////////////////////////////////////   
    // CMyDlg message handlers   
      
    BOOL CMyDlg::OnInitDialog()   
    {   
        CDialog::OnInitDialog();   
      
        // Add "About..." menu item to system menu.   
      
        // IDM_ABOUTBOX must be in the system command range.   
        ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);   
        ASSERT(IDM_ABOUTBOX < 0xF000);   
      
        CMenu* pSysMenu = GetSystemMenu(FALSE);   
        if (pSysMenu != NULL)   
        {   
            CString strAboutMenu;   
            strAboutMenu.LoadString(IDS_ABOUTBOX);   
            if (!strAboutMenu.IsEmpty())   
            {   
                pSysMenu->AppendMenu(MF_SEPARATOR);   
                pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);   
            }   
        }   
      
        // Set the icon for this dialog.  The framework does this automatically   
        //  when the application's main window is not a dialog   
        SetIcon(m_hIcon, TRUE);         // Set big icon   
        SetIcon(m_hIcon, FALSE);        // Set small icon   
           
        // TODO: Add extra initialization here   
        /*  
        CRect rect,rect_1;    
        m_rang.GetWindowRect(&rect);  
        GetWindowRect(&rect_1);  
        rect_1.right=rect.right+2;  
        SetWindowPos(NULL,0,0,rect_1.Width(),rect_1.Height(),  
                SWP_NOMOVE | SWP_NOZORDER);  
                */  
        m_rang.GetWindowRect(&rectrang_1);   
        GetWindowRect(&rectLarge);   
        rectSmall.top=rectLarge.top;   
        rectSmall.left=rectLarge.left;   
        rectSmall.right=rectrang_1.right;   
        rectSmall.bottom=rectLarge.bottom;   
        //默认为FIFO算法   
        m_suanfa=0;   
        UpdateData(FALSE);   
        return TRUE;  // return TRUE  unless you set the focus to a control   
    }   
      
    void CMyDlg::OnSysCommand(UINT nID, LPARAM lParam)   
    {   
        if ((nID & 0xFFF0) == IDM_ABOUTBOX)   
        {   
            CAboutDlg dlgAbout;   
            dlgAbout.DoModal();   
        }   
        else  
        {   
            CDialog::OnSysCommand(nID, lParam);   
        }   
    }   
      
    // If you add a minimize button to your dialog, you will need the code below   
    //  to draw the icon.  For MFC applications using the document/view model,   
    //  this is automatically done for you by the framework.   
      
    void CMyDlg::OnPaint()    
    {   
        if (IsIconic())   
        {   
            CPaintDC dc(this); // device context for painting   
      
            SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);   
      
            // Center icon in client rectangle   
            int cxIcon = GetSystemMetrics(SM_CXICON);   
            int cyIcon = GetSystemMetrics(SM_CYICON);   
            CRect rect;   
            GetClientRect(&rect);   
            int x = (rect.Width() - cxIcon + 1) / 2;   
            int y = (rect.Height() - cyIcon + 1) / 2;   
      
            // Draw the icon   
            dc.DrawIcon(x, y, m_hIcon);   
        }   
        else  
        {   
            CDialog::OnPaint();   
        }   
        CDC *pDC = GetWindowDC();   //获取窗口DC   
        CDC *memDC  =   new   CDC;   //定义兼容DC   
    //  if(flag)   
    //  {   
            memDC->CreateCompatibleDC(pDC);   
        //加载位图   
        CBitmap pBit;   
        pBit.LoadBitmap(IDB_BITMAP1);   
        CBitmap *pOldBit;   
        //选位图进memDC   
        pOldBit=(CBitmap *)memDC->SelectObject(&pBit);   
        CRect rect;   
        CRect rectrang;   
        m_rang.GetWindowRect(&rectrang);   
        GetWindowRect(&rect);   
        rect.right=rectrang.right;   
        BITMAP bitmap;   
        pBit.GetBitmap(&bitmap);   
        //pDC->BitBlt(0,0,rect.Width(),rect.Height(),memDC,0,0,SRCCOPY);   
        pDC->StretchBlt(0,0,rect.Width(),rect.Height(),memDC,0,0,bitmap.bmWidth,bitmap.bmHeight,SRCCOPY);   
        memDC->SelectObject(pOldBit);   
        pDC->SetBkMode(TRANSPARENT);   
    //  flag=false;   
           
    //  }   
    }   
      
    // The system calls this to obtain the cursor to display while the user drags   
    //  the minimized window.   
    HCURSOR CMyDlg::OnQueryDragIcon()   
    {   
        return (HCURSOR) m_hIcon;   
    }   
      
    void CMyDlg::OnMouseMove(UINT nFlags, CPoint point)    
    {   
        // TODO: Add your message handler code here and/or call default   
           
        if(point.x>= rectSmall.right-10)  //扩展   
        {   
               
            SetWindowPos(NULL,0,0,rectLarge.Width(),rectLarge.Height(),   
                SWP_NOMOVE |  SWP_NOZORDER);   
            if(flag)   
            {   
            this->Invalidate(FALSE);   
            flag=false;  //只闪烁一次   
            }   
        }   
        else   //收缩   
        {   
            SetWindowPos(NULL,0,0,rectSmall.Width(),rectSmall.Height(),   
                SWP_NOMOVE |  SWP_NOZORDER);   
            flag=true;   
        }   
        //this->Invalidate(FALSE);   
        CDialog::OnMouseMove(nFlags, point);   
    }   
      
      
    void CMyDlg::Onqueding()    
    {   
        UpdateData();   
        CListCtrl *m_list = new CListCtrl();   
        m_list->Create(WS_CHILD | WS_VISIBLE |LVS_REPORT,CRect(20,20,545,400),this,102);   
        //改为网状风格   
        DWORD dwStyle=m_list->GetExtendedStyle();   
        dwStyle |= LVS_EX_FULLROWSELECT;  //整行高亮所选中的行只适用Report Style   
        dwStyle |= LVS_EX_GRIDLINES;           //网格线. 只适用Report Style   
        m_list->SetExtendedStyle(dwStyle );   
           
        m_list->SetBkColor(RGB(50,200,50));//绿背景色   
        m_list->SetTextColor(RGB(0,0,220)); //蓝文本色   
        m_list->SetTextBkColor(RGB(50,200,50));  //绿文本背景色   
        m_list->InsertColumn(0,"访问序列",LVCFMT_LEFT,75);   
      
        ////////////////////////////////////////////   
        int m_proc=this->GetDlgItemInt(IDC_COMBO1);  //获取组合框文本   
        int m_mem=this->GetDlgItemInt(IDC_COMBO2);   
        int stay;   
        CString cs;   
        bool flag1=true;   
        if(m_mem)  //有值才动态定义   
        {   
            mem = new int[m_mem];   //内存分配数组   
            memset(mem,-1,sizeof(int)*m_mem);  //初始化为-1   
            count = new int[m_mem];   //标记驻留次数   
            memset(count,0,sizeof(int)*m_mem);   //初始化为0   
        }   
           
        if(m_proc)   
        {          
            for(j=1;j<19;j++)   //初始化列   
            {   
                visit[j]=rand()%m_proc;    //访问序列初始化   
                   
                cs.Format("%d",visit[j]);   
                m_list->InsertColumn(j,cs,LVCFMT_LEFT,25);   
            }   
        }   
        for(k=0;k<m_mem;k++)    //初始化行，分配页   
        {   
            char cha[2];   
            itoa(k,cha,10);   
            cs="内存第页";  //汉字双字节，注意   
            cs.Insert(6,cha);   
            m_list->InsertItem(k,cs);   
               
        }   
        if(m_mem &&m_proc)   
        {   
            for(i=1;i<19;i++)  //列   
            {   
                for(k=0;k<m_mem;k++,i++)    //行   
                {   
                    ////////////////////////////////////////   
                    for(j=0;j<m_mem;j++)   //找出相等的内存页visit[i]与所有行比较   
                        if(mem[j]==visit[i])   //若相等马上输出所有行   
                        {   
                            switch(m_suanfa)   
                            {   
                            case 1:   //FIFO变为LRU只需把逗留数组count置为0就可以了   
                                count[j]=0;   //相同的内存页把逗留次数置0   
                                break;   
                            }   
                            for(m=0;m<m_mem;m++)  //输出   
                            {      
                                if(mem[m]!=-1)   
                                {   
                                    cs.Format("%d",mem[m]);   
                                    m_list->SetItemText(m,i,cs);   
                                    count[m]++;   
                                       
                                }   
                            }   
                            k--;   
                            flag1=false;   
                            break;//找到相等的先输出所有行，，然后跳出   
                        }   
                        ///////////////////////////////////////    
                        if(flag1)      
                        {      
                            switch(m_suanfa)   
                            {   
                            case 0: //FIFO   
                            case 1: //LRU   
                                if(mem[m_mem-1]!=-1)    //内存页满，开始置换   
                                {   
                                    stay=FIFO(count,m_mem);   //谁的逗留时间最长   
                                       
                                    mem[stay]=visit[i];   //最长的被置换   
                                    count[stay]=0;   //逗留次数清零   
                                }   
                                else    //内存页还没用完   
                                {   
                                    mem[k]=visit[i];   
                                }                                                  
                                    break;   
                            case 2:  //OPT   
                                if(mem[m_mem-1]!=-1)    //内存页满，开始置换   
                                {   
                                    stay=OPT(mem,i,m_mem,visit);   //谁的逗留时间最长   
                                       
                                    mem[stay]=visit[i];   //最长的被置换   
                                }   
                                else    //内存页还没用完   
                                {   
                                    mem[k]=visit[i];   
                                }   
                                   
                                    break;   
                            }//switch   
                            for(m=0;m<m_mem;m++)  //输出所有行   
                                    if(mem[m]!=-1)   
                                    {   
                                        CString cst;   
                                        cst.Format("%d",mem[m]);   
                                        m_list->SetItemText(m,i,cst);   
                                        count[m]++;  //标记停留次数   
                                    }   
                        }   
                        flag1=true;   
                ///////////////////////////////////////            
                }//for(k   
                if(k==m_mem) i--;  //有两个i++   
            }//for(i   
            delete []count;   
            delete []mem;   
        }//if   
        UpdateData(FALSE);   
    }   
      
    int FIFO(int *count_0,int num)   
    {   
        int Max=count_0[0];   
        int Max_stay=0;   
        for(int n=1;n<num;n++) //找出最大数的下标   
         if(Max < count_0[n])   
            {   
                Max=count_0[n];   
                Max_stay=n;   
            }   
            return Max_stay;   
    }   
    int *L;   
    int OPT(int *temp_mem,int i,int num,int *vis)   
    {   
        int Max;   
        int Max_stay;   
        int p=i+1;   
        L = new int[num];   
        memset(L,0,sizeof(int)*num);  //从0开始   
        for(int n=0;n<num;n++)   
            for(i=p;i<19;i++)  //下一个开始比   
            if(temp_mem[n]!=vis[i]) L[n]++;   
            else break;   
            Max=L[0];   
            Max_stay=0;   
            for(int h=0;h<num;h++)   //找出最大数的下标   
            {   
               
                if(Max < L[h])   
                {   
                    Max=L[h];   
                    Max_stay=h;   
                }   
            }   
                delete []L;   
        return Max_stay;   
    }   
